#include "list.h"
int userID = 0;      //用户ID
struct node * createLists(struct node *pHead){  //创建一个链表的头结点
     pHead = malloc(sizeof(struct node));
     pHead->pPre = pHead;
     pHead->pNext = pHead;
     return pHead;
}

USER * createUser(){
    USER * pUser=(USER *)malloc(sizeof(USER));
    pUser->id=++userID;
    printf("输入注册用户名：\n");
    scanf("%s",pUser->name);
    printf("输入密码：\n");
    scanf("%s",pUser->password);
    return pUser;
}

struct node *create(void * data){              //创建链表结点
    struct node *pNew= malloc(sizeof(struct node)); //开辟一个地址空间赋值给新指针（地址）
    pNew->pData = data ;    //存入输入的数据
    pNew->pPre = NULL ;  // 将该指向置为NULL
    pNew->pNext = NULL ;  // 将该指向置为NULL
    return pNew;
}

void add(struct node *pHead,void * data){    //添加链表元素
    struct node *pNew = create(data);
        if (pHead->pNext == pHead)  //判断头结点后是否有地址（指针），无指针情况
        {                         // head.pPre始终为尾结点
            pHead->pNext = pNew;   //将头结点指向新指针（地址）
            pNew->pPre = pHead;   //将新加的指针，前指向头指针
            pHead->pPre = pNew;      //将尾节点更新为新加指针
            pNew->pNext = pHead ;  //将尾节点指向新指针（地址）
        }
        else      //头指针后面有指针情况下
        {         
            pHead->pPre->pNext = pNew;   //将之前的 尾结点的后部 指向新指针
            pNew->pPre= pHead->pPre;  //将新指针的 前部指向 原来的尾结点
            pHead->pPre = pNew;  // 将原来尾结点的指向，指到新建指针（地址）
            pNew->pNext = pHead;    // 将新指针的 后部 指向头结点
        }
   }

void insert(struct node *pHead,int index,void * data){      //插入链表元素
    struct node *p =pHead;     //保存头结点地址
    while (p->pNext!=pHead&&index!=0)      //终止条件为 找到要插入点的前一个，或者找到该链表最后一个
    { 
        p = p->pNext;             //后移
        index--;              
    }
    if(index!=0)       //index不为0，则下标越界
    {
        printf("下标错误，非插入操作，无法找到对应位置！");     
    }
    else{
        struct node *pNew = create(data);
        pNew->pNext = p->pNext;             //将插入指针的 后部 指向插入点
        p->pNext->pPre = pNew;     //不为头，将插入点指针 前部 指向插入指针
        p->pNext = pNew;      //插入指针放入插入位置
        pNew->pPre = p;         //插入指针 前部 指向插入点前一个
    }
}

void  delete(struct node *pHead,int index){        //删除链表元素
     struct node * p = pHead;
     while(index!=0&&p->pNext!=pHead)
     {
          index--;
          p=p->pNext;
     }
     if(p->pNext==pHead||index!=0)
     {
          printf("index所代表的位置不存在\n");
     }
     else
     {
        free(p->pNext);
        p->pNext = p->pNext->pNext;
        p->pNext->pNext->pPre = p;
     }
}

//树的相关
TD * createTree(char cData){
    TD *pRt = malloc(sizeof(TD));
    pRt->cData =cData;
    pRt->tLeft =NULL;
    pRt->tRight =NULL;
    return pRt;
}

TD * iData(char * parr,int leng, int num){
    if (num>=leng)
    {
        return NULL;
    }
    TD *pRoot = createTree(parr[num]);
    pRoot->tLeft = iData(parr,leng,2*num);
    pRoot->tRight = iData(parr,leng,2*num+1);
    return pRoot;
}

void printLevel(TD * pRoot){
    struct node * pHead = createLists(pHead);
    add(pHead,pRoot);
    while (pHead->pNext!=pHead)
    {
    TD * q =  pHead->pNext->pData;
    printf("%c--",*(char*)q);
    if (q->tLeft!=NULL) 
    {
        add(pHead,q->tLeft);
    }
    if (q->tRight!=NULL)
    {
        add(pHead,q->tRight);
    }
   // printf("%c--",*(char*)q);
    delete(pHead,0);
        
    }
}

TD * createSeachTree(char * pArr, int len)
{
     //根据num的值来创建节点,num就是元素在数组中的编号
     TD * pNode =  createTree(pArr[0]);
     //遍历数组中所有的元素
     for (size_t i = 1; i < len; i++)
     {
          //定义一个临时指针等于根节点
          TD * pTemp = pNode;

          //和元素进行比较，如果比元素大就该往元素的右边继续比较或者找位置
          while (1)
          {
               //如果大于说明往右走
               if(pArr[i]>pTemp->cData)
               {
               //如果进行比较的元素的左子结点为空，就可以在这里存下来
                    if(pTemp->tRight==NULL)
                    {
                         printf("%c落在了%c的右边\n",pArr[i],pTemp->cData);
                         pTemp->tRight = createTree(pArr[i]);
                         break;
                    }
                    else
                    {
                         //节点往左边移动
                         pTemp = pTemp->tRight;
                    }                    
               }
               else
               {
                    //如果进行比较的元素的左子结点为空，就可以在这里存下来
                    if(pTemp->tLeft==NULL)
                    {
                         printf("%c落在了%c的左边\n",pArr[i],pTemp->cData);
                         pTemp->tLeft = createTree(pArr[i]);
                         break;
                    }
                    else
                    {
                         //节点往左边移动
                         pTemp = pTemp->tLeft;
                    }
               }
          }
          
     }
     return pNode;
}

int searchTreeNode(TD *pRoot,char word){
        int num = 0;
        TD * temp = pRoot;
        while (temp->tLeft!=NULL||temp->tRight!=NULL)
        {
            if (word>temp->cData)
            {  temp = temp->tRight;
                num++;
            }
            else
            {
                temp = temp->tLeft;
                num++;
            }
            if (word==temp->cData)
               {
                printf("找到了该值！\n");
                printf("共找了%d次\n",num);
                return 0;
               }
        }
}

//单独运行主函数
// int main(int argc,const char * argv[])
// { 
//      char arr[]={'a','b','c','d','e','f','g'};
//     TD * p = createSeachTree(arr,7);
//     searchTreeNode(p,'c');
//     // TD * pRoot = iData(arr,sizeof(arr),1);
//     // char * pa = arr;
//     // printLevel(pRoot); 
//     // putchar(10);
//     return 0;
// }